package _interview100;

import _object.TreeNode;

/**
 * 437. 路径总和 III
 */
public class No437 {
    private int ans;

    public int pathSum(TreeNode root, int targetSum) {
        if (root == null) return 0;
        dfs(root, targetSum);
        pathSum(root.left, targetSum);
        pathSum(root.right, targetSum);
        return ans;
    }

    public void dfs(TreeNode root, long targetSum) {
        if (root == null) return;
        if (targetSum == root.val) ans++;
        dfs(root.left, targetSum - root.val);
        dfs(root.right, targetSum - root.val);
    }
}
